문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 외판원 순회 문제 (문단 편집) === [[동적 계획법]]으로 풀기 === 외판원 순회 문제의 최적해는 [[동적 계획법]]으로 지수 시간에 풀 수 있다. 다음은 동적 계획으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.{{{#!syntax python def travel (W): n = len(W) - 1 size = 2 ** (n - 1) D = [[0] * size for _ in range(n + 1)] P = [[0] * size for _ in range(n + 1)] for i in range(2, n + 1): D[i][0] = W[i][1] for k in range(1, n - 1): for A in range(1, size): if (count(A, n) == k): for i in range(2, n + 1): if (not isIn(i, A)): D[i][A], P[i][A] = minimum(W, D, i, A) A = size - 1 D[1][A], P[1][A] = minimum(W, D, 1, A) return D, P def minimum (W, D, i, A): minValue = INF minJ = 1 n = len(W) - 1 for j in range(2, n + 1): if (isIn(j, A)): m = W[i][j] + D[j][diff(A, j)] if (minValue > m): minValue = m minJ = j return minValue, minJ }}}저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기